package com.peng.leetcode.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * CanFinish
 * 207. 课程表
 * 你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
 *
 * 在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
 *
 * 给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
 *
 * 链接：https://leetcode-cn.com/problems/course-schedule
 *
 * @author: lupeng6
 * @create: 2020/12/31 18:44
 */
public class CanFinish {

    public static void main(String[] args) {
        int[][] prerequisites = {{0, 1}, {0, 3}, {1, 4}, {2, 4}, {1, 3}, {3, 4}};
        canFinish(5, prerequisites);
    }

    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] inDegree = new int[numCourses];
        List<List<Integer>> adjacency = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adjacency.add(new ArrayList<>());
        }

        for (int i = 0; i < prerequisites.length; i++) {
            int[] prerequisite = prerequisites[i];
            int i1 = prerequisite[0];
            int i2 = prerequisite[1];
            inDegree[i1]++;
            adjacency.get(i2).add(i1);
        }

        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < inDegree.length; i++) {
            int i1 = inDegree[i];
            if (i1 == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            Integer pre = queue.poll();
            numCourses--;
            List<Integer> adj = adjacency.get(pre);
            for (Integer integer : adj) {
                inDegree[integer]--;
                if (inDegree[integer] == 0) {
                    queue.offer(integer);
                }
            }
        }
        return numCourses == 0;
    }

}
